/**
 * @(#) SwapTree.java Mar 23, 2010 2:34:27 PM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package tree;

import java.util.Stack;

import javax.swing.tree.TreeNode;


/**
 * Class <code>SwapTree</code>
 * 
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Mar 23, 2010 2:34:27 PM
 * 
 */
public class SwapTree
{

	public static Stack bfs(BinaryNode root)
	{
		if (root == null)
			return null;

		Stack<BinaryNode> stack = new Stack();
		Stack<BinaryNode> full = new Stack();
		BinaryNode tmp;
		stack.push(root);
		full.push(root);

		while (!stack.empty())
		{
			tmp = stack.pop();

			if (tmp.left != null)
			{
				stack.push(tmp.left);
				full.push(tmp.left);
			}
			if (tmp.right != null)
			{
				stack.push(tmp.right);
				full.push(tmp.right);
			}

		}

		return full;
	}

	public static BinaryNode swap(BinaryNode root)
	{
		Stack<BinaryNode> stack = bfs(root);
		BinaryNode newroot = new BinaryNode();
		BinaryNode tmp = new BinaryNode();
		while (!stack.empty())
		{
			newroot = stack.pop();
			if (newroot.left != null || newroot.right != null)
			{
				tmp = newroot.left;
				newroot.left = newroot.right;
				newroot.right = tmp;
			}

		}

		return newroot;
	}
	
	void MirrorRecursively(Node pNode)
	{
	      if(pNode == null)
	            return;

	      // swap the right and left child sub-tree
	      Node pTemp = pNode.left;
	      pNode.left = pNode.right;
	      pNode.right = pTemp;

	      // mirror left child sub-tree if not null
	      if(pNode.left != null)
	            MirrorRecursively(pNode.left);  

	      // mirror right child sub-tree if not null
	      if(pNode.right != null )
	            MirrorRecursively(pNode.right); 
	}

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		BinarySearchTree t = new BinarySearchTree( );
		t.insert(1);
        t.insert(8);
        t.insert(6);
        t.insert(3);
        t.insert(9);
        SwapTree.bfs(t.root);
        t.printInOrder(SwapTree.swap(t.root));
        
	}

}
